package ca.ulaval.ift.gloo.SimSolution.model;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Implementation de l'algorithme du plus court chemin(DIJKSTRA)
public class Itineraire {
	private Collection<Noeud> noeuds;
	private Collection<Arc> arcs;
	private Collection<Noeud> visite;
	private Collection<Noeud> nonVisite;
	private Collection<Noeud> chemin;
	private Map<Noeud, Float> distance;
	
	private Plan plan;
	
	public Itineraire(){
		
	}
	
	public void execute(Noeud source, Noeud destination) {
		
		plan  = Plan.getInstance();
		noeuds = plan.getListeNoeuds();
		arcs = plan.getListeArcs();
		visite = new ArrayList<Noeud>();
		nonVisite = new ArrayList<Noeud>();
		distance = new HashMap<Noeud, Float>();
		
		
		for(Noeud n : noeuds){
			distance.put(n, Float.MAX_VALUE);
		}
		
		distance.put(source, new Float(0));
		nonVisite.add(source);
		
	    while (nonVisite.size() > 0) {
	    	Noeud tmp = recupererNoeudLePlusProche();
	    	visite.add(tmp);
	    	nonVisite.remove(tmp);
	    	//On s'arrête lorsqu'on a trouvé la destination
	    	if(tmp.equals(destination))
	    		nonVisite.clear();
	    	else
	    		visiterSuivants(tmp);
	    }
	}
	
	
	//permet de récupérer le noeud le plus proche dans la liste nonVisite
	public Noeud recupererNoeudLePlusProche(){
		Noeud plusProche = null;
		for(Noeud n : nonVisite){
			if(plusProche == null || (distance.get(n) < distance.get(plusProche)))
				plusProche = n;		
		}
		
		return plusProche;
	}
	
	public void visiterSuivants(Noeud noeud){
		List<Noeud> suivants = recupererSuivant(noeud);
		
		for(Noeud n : suivants){
			if(distance.get(n) < (distance.get(noeud) + getDistance(noeud, n)) ){
				distance.put(n, distance.get(noeud) + getDistance(noeud, n));
				chemin.add(n);
				nonVisite.add(n);
			}	
		}
	}
	
	public List<Noeud> recupererSuivant(Noeud noeud) {
		List<Noeud> result = new ArrayList<Noeud>();
		
		for(Arc a : arcs){
			if(a.getExt1().equals(noeud) && ! visite.contains(a.getExt2()))
				result.add(a.getExt2());
			else if(a.getExt2().equals(noeud) && ! visite.contains(a.getExt1()))
				result.add(a.getExt1());
		}
		
		return result;
	}
	
	public float getDistance(Noeud n1, Noeud n2){
		
		for(Arc a : arcs){
			if(a.isExtremite(n1) && a.isExtremite(n2))
				return a.getDistance();
		}
		
		return Float.MAX_VALUE;
	}
}
